//
// Created by dengspc on 2019/2/13.
//

#ifndef INC_010_ALGORITHM_ADJGRAPH_H
#define INC_010_ALGORITHM_ADJGRAPH_H

#include <iostream>
#include <cassert>
#include <queue>
#include <stack>
#include "Graph.h"
#include "Bag.h"

#define BLACK false
#define WHITE true

using namespace std;
typedef bool Color;

class AdjGraph:public DiGraph{
private:
    int v;//顶点（vertex）数量
    int e;//边数量（edge)
    Bag<int>* adjs;//背包数组，下标对应顶点序号，包里面的数据是与此顶点直接连接的顶点集合
public:
    AdjGraph(int v = 0){
        this->v=v;
        this->e = 0;
        adjs = new Bag<int>[v];
        for (int i =0; i < v; ++i) {
            adjs[i] = *(new Bag<int>());
        }
    }

    ~AdjGraph(){
        delete[] adjs;
    }

    int V() {
        return v;
    }//求顶点数量
    int E() {
        return e;
    }//求边数量
    void addEdge(int v, int w) {
        assert(v<this->v);
        assert(w<this->v);
        adjs[v].add(w);
        adjs[w].add(v);
        e++;
    }//向图中添加一条边 v w
    vector<int>* adj(int v) {
        return adjs[v].getVector();
    }//与v相邻的顶点集合
    void print() {
        cout<<this->v<< " vertices, " << this->e << " edges" << endl;
        cout<<"numOfSelfLoops: " << numOfSelfLoops()<<endl;
        for (int i =0; i < this->v; ++i) {
            cout<< i << ": ";
            vector<int>* vector1 = adj(i);
            int size = vector1->size();
            for (int j =0; j < size; ++j) {
                cout << (*vector1)[j] << " ";
            }
            cout<< " degree = "<< degree(i) <<endl;
            delete vector1;
        }
        cout<< "maxDegree = "<< maxDegree() <<endl;
        cout<< "avgDegree = "<< avgDegree() <<endl;

    }//打印
    int numOfSelfLoops() {
        int count =0;
        for (int i =0; i < V(); i++) {
            vector<int>* vector1 = adj(i);
            int size = vector1->size();
            for (int j =0; j < size; ++j) {
                if((*vector1)[j] == i)
                    count++;
            }
            delete vector1;
        }
        return count/2;
    }//计算自环的个数
};

/**
 * 参考命题A
 */
class DepthFirstSearch:public Search{
private:
    bool* marks;///标记对应点是否被访问过 true = 访问过
    int count;//与source连通的顶点数量，也就是source所在连通分量的顶点数量

    void dfs(AdjGraph* g, int source){
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            if(!marks[(*vector1)[i]]){
                marks[(*vector1)[i]] = true;
                count++;
                dfs(g,(*vector1)[i]);
            }
        }

        delete vector1;
    }
public:
    DepthFirstSearch(AdjGraph*  g, int source){
        marks = new bool[g->V()];
        count = 1;
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        dfs(g,source);
    }

    ~DepthFirstSearch(){
        delete[] marks;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通
    int size() {
        return count;
    } // 与 source联通的source总数
};

/**
 * 参考命题A续
 * 深度优先搜索，不能得到最短路径
 * 图路径算法
 */
class DepthFirstPaths:public Paths{
private:
    void dfs(AdjGraph* g, int source){
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            int pos = (*vector1)[i];
            if(!marks[pos]){
                marks[pos] = true;
                edges[pos] = source;
                dfs(g,pos);
            }
        }

        delete vector1;
    }
public:
    DepthFirstPaths(AdjGraph*  g, int source){
        marks = new bool[g->V()];
        edges = new int[g->V()];
        this->source = source;
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        dfs(g,source);
    }

    ~DepthFirstPaths(){
        delete[] marks;
        delete[] edges;
    }
};




/**
 * 广度优先搜索
 */
class BreadthFirstPaths:public Paths{
private:
    queue<int>* queue1;
    void bfs(AdjGraph* g, int s){
        queue1->push(s);
        while(!queue1->empty()) {
            int source = queue1->front();
            queue1->pop();
            vector<int> *vector1 = g->adj(source);
            int size = vector1->size();
            for (int i = 0; i < size; ++i) {
                int pos = (*vector1)[i];
                if (!marks[pos]) {
                    queue1->push(pos);
                    marks[pos] = true;
                    edges[pos] = source;
                }
            }
            delete vector1;
        }

    }
public:
    BreadthFirstPaths(AdjGraph*  g, int source){
        marks = new bool[g->V()];
        edges = new int[g->V()];
        this->source = source;
        this->queue1 = new queue<int>();
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        bfs(g,source);
    }

    ~BreadthFirstPaths(){
        delete[] marks;
        delete[] edges;
        delete queue1;
    }
};


/**
 * 连通分量
 */
class DepthFirstCC:public CC{
private:
    bool* marks;//标记对应点是否被访问过 true = 访问过
    int* ids;//下标对应顶点序号，值对应为所在连通分量的序号
    int counts = 0;//图g的连通分量的数量

    void dfs(AdjGraph* g, int v){
        marks[v] = true;
        ids[v] = counts;
        vector<int>* vector1 = g->adj(v);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            if(!marks[(*vector1)[i]]){
                dfs(g,(*vector1)[i]);
            }
        }

        delete vector1;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通

public:
    DepthFirstCC(AdjGraph*  g){
        marks = new bool[g->V()];
        ids = new int[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        //遍历所有顶点
        for (int i = 0 ; i < g->V(); ++i) {
            if(!marks[i]){
                dfs(g,i);//遍历i所在连通分量的顶点，并标记在ids数组中
                counts++;//连通分量数量增加
            }
        }
    }

    ~DepthFirstCC(){
        delete[] marks;
        delete[] ids;
    }

    bool connected(int v, int w){
        return ids[v] = ids[w];
    }//v 与 w 是否连通
    int count(){
        return counts;
    }// 连通分量的数量
    int id(int v){
        return ids[v];
    }// v所在连通分量的顶点(标识符)

};

/**
 * 图存在环？（除去平行边和自环）
 */
class DfsCycle:public Cycle{
private:
    bool* marks;///标记对应点是否被访问过 true = 访问过
    bool hasCycles;

    /**
     * 能被dfs访问的，肯定在同一个连通分量里面
     * @param g
     * @param source
     * @param preSource
     */
    void dfs(AdjGraph* g, int source, int preSource){
        marks[source] = true;
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            int w = (*vector1)[i];
            if(!marks[w]){
                dfs(g,w,source);
            }else if(w!=preSource) {//当前节点（w）被访问过 且 与前一个节点不等（ 除去 W - V 然后 V - W这种情况）
                hasCycles = true;
                break;
            }
        }

        delete vector1;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通

public:
    DfsCycle(AdjGraph*  g){
        hasCycles = false;
        marks = new bool[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        for (int i = 0 ; i < g->V(); ++i) {
            if(!marked(i))
                dfs(g,i,i);
        }
    }

    ~DfsCycle(){
        delete[] marks;
    }

    bool hasCycle() {
        return hasCycles;
    }
};


/**
 * 图为二分图？
 */
class DfsTwoColor:public TwoColor{
private:
    bool* marks;///标记对应点是否被访问过 true = 访问过
    Color * colors;//标记为两个颜色
    bool isTwoColorable = true;//初始化为二分树

    /**
     * 能被dfs访问的，肯定在同一个连通分量里面
     * @param g
     * @param source
     * @param preSource
     */
    void dfs(AdjGraph* g, int source, Color color){
        marks[source] = true;
        colors[source] = color;
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            int w = (*vector1)[i];
            if(!marks[w]){
                dfs(g,w,!color);
            }else if(colors[w] == colors[source]){
                isTwoColorable = false;
                return ;
            }
        }

        delete vector1;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通

public:
    DfsTwoColor(AdjGraph*  g){
        marks = new bool[g->V()];
        colors = new bool[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
            colors[i] = BLACK;
        }
        for (int i = 0 ; i < g->V(); ++i) {
            if(!marked(i))
                dfs(g,i,BLACK);
        }
    }

    ~DfsTwoColor(){
        delete[] marks;
        delete[] colors;
    }

    bool isBipartite() {
        return isTwoColorable;
    }
};

#endif //INC_010_ALGORITHM_ADJGRAPH_H
